package leetcodeHis.链表;

import java.util.List;

/**
 * @Author zhang lei
 * @Date 2022-01-05 16:20
 * 链表排序
 */
class Algo148 {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(1);
        listNode.next.next.next = new ListNode(3);
        ListNode resutl = sortList(listNode);
    }

    private static ListNode sortList(ListNode head) {
        ListNode ya = new ListNode(-1);
        ya.next = head;

        while (ya.next != null) {
            ListNode aPre = ya;
            ListNode a = ya.next;

            ListNode bPre = ya;
            ListNode b = ya.next;
            while (b != null) {
                if(a.val > b.val) {
                    ListNode bNext = b.next;
                    ListNode aNext = a.next;
                    aPre.next = b;
                    b.next = aNext;
                    bPre.next = a;
                    a.next = bNext;

                    bPre = a;
                    b = a.next;
                    continue;
                }
                bPre = b;
                b = b.next;
            }
            ya = ya.next;
        }
        return ya.next;
    }
}
